#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    bool hasIncreasingSubArr(vector<int>& nums, int k){
        int n=nums.size();
        auto check=[&](int idx){
            for(int i=1;i<k;i++)
                if(nums[idx+i]<=nums[idx+i-1]) return false;
            return true;
        };
        for(int i=0;i+k*2<=n;i++)
            if(check(i)&&check(i+k)) return true;
        return false;
    }
};

class Solution2{
public:
    int maxIncreasing(vector<int>& nums){
        int ans=0, pre_cnt=0, cnt=0;
        for(int i=0;i<nums.size();i++){
            cnt++;
            if(i==nums.size()-1||nums[i]>=nums[i+1]) {
                ans=max({ans, cnt/2, min(pre_cnt, cnt)});
                pre_cnt=cnt;
                cnt=0;
            }
        }
        return ans;
    }
};

class Solution3{
public:
    int sumOfGood(vector<int>& nums){
        const int MOD=1e9+7;
        unordered_map<int,int>f, cnt;
        for(int x: nums){
            long long c=cnt[x-1]+cnt[x+1]+1;
            f[x]=(x*c+f[x]+f[x-1]+f[x+1])%MOD;
            cnt[x]=(cnt[x]+c)%MOD;
        }
        long long ans=0;
        for(const auto& [_,s]:f) ans+=s;
        return ans%MOD;
    }
};

// 计数dp， bit
class Solution4 {
public:
    int countKReducibleNumbers(string s, int k) {
        const int MOD=1e9+7;
        int n=s.length();
        vector<vector<int>> memo(n,vector<int>(n,-1));
        function<int(int,int,bool)> dfs=[&](int i, int left1, bool is_limit) -> int {
            if(i==n) return !is_limit&&left1==0;
            if(!is_limit&&memo[i][left1]!=-1) return memo[i][left1];
            int up=is_limit ? s[i] - '0' : 1;
            int res=0;
            for(int d=0;d<=min(up, left1);d++){
                res=(res+dfs(i+1,left1-d,is_limit&&d==up))%MOD;
            }
            if(!is_limit) memo[i][left1]=res;
            return res;
        };
        long long ans=0; vector<int> f(n);
        for(int i=1;i<n;i++){
            f[i]=f[__builtin_popcount(i)]+1;
            if(f[i]<=k) ans+=dfs(0,i,true);
        }
        return ans%MOD;
    }
};

int main(){
    vector<int> nums={2,5,7,8,9,2,3,4,3,1};
    Solution s; cout<<s.hasIncreasingSubArr(nums, 3)<<endl;
    vector<int> nums2={2,5,7,8,9,2,3,4,3,1};
    Solution2 s2; cout<<s2.maxIncreasing(nums2)<<endl;
    vector<int> nums3={1,2,1};
    Solution3 s3; cout<<s3.sumOfGood(nums3)<<endl;
    Solution4 s4; cout<<s4.countKReducibleNumbers("111",1)<<endl;

}